//1.On
class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()==1)
            return 0;
        int steps=0;
        int current_end = 0;  // 当前阶段的最远边界，每个边界里面移动只算一步
        int max_dis = 0;    //当前可达最远距离
        int n = nums.size();
        for(int i = 0; i < n - 1; ++i) {
            //[2,3,1,2,8,1,1,1,1,5]
            max_dis = max(max_dis, i + nums[i]);
            if(current_end == i) {  //走到当前的最远边界，才会跳下一步
                steps++;
                current_end=max_dis;
                if(max_dis >= n - 1) 
                    break;
            }
           
           
        }
        return steps;
    }
};

//2.反向查找出发位置(时间复杂度略高 On^2)
class Solution {
public:
    int jump(vector<int>& nums) {
        int position = nums.size() - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
};





